package shuanfa;

public class Knapsack01 {
    static int N=6;//物品有五件 初始边界为0
    static int W=21;//背包容量为20 初始边界为0
    static int weight[]= {0,2,3,4,5,9};//重量 2 3 4 5 9
    static int value[]= {0,3,4,5,8,10};//价值3 4 5 8 10
    public static void main(String[] args) {
        int knapsack = knapsack1(N, W, weight, value);
        System.out.println(knapsack);
    }
    private static int knapsack(int N,int W,int[] weight,int[] value){
        int[][] dp = new int[N][W];
        for (int i = 1 ;i<N;i++){
            for (int j = 1 ; j< W;j++){
                if (weight[i]>j){//太重了，拿不了
                    dp[i][j] = dp[i-1][j];
                }else {
                    dp[i][j] = Math.max(dp[i-1][j],value[i] + dp[i-1][j-weight[i]]);
                }
            }
        }
        return dp[N-1][W-1];
    }
    private static int knapsack1(int N,int W,int[] weight,int[] value){
        int[] dp = new int[W];//滚动数组压缩
        for (int i = 1 ;i<N;i++){
            for(int j=W-1;j>=1;j--) {//重点 反过来遍历填充
                if(weight[i]<=j) {
                    dp[j]=Math.max(dp[j], dp[j-weight[i]]+value[i]);
                }
            }
        }
        return dp[W-1];
    }
}
